CF1267J Just Arrange the Icons

复杂度并不“显然”的一道偏思维题

题解：

首先要发现对于已知的单面容量$k$和面数$p$，其可承载的合法总容量是可以定量计算的一段连贯的区间，即$[(k-1)p,kp]$

其次，对于已知的同种类软件数$m$，若给出$k$，其所需的$p$也是唯一的（合法的前提下）,即$p=\lfloor\frac{m-1}{k}\rfloor+1$，而是否合法的判定又可以套用上方的公式

(解释一下第2个式子：贪心的装满每一面，剩余的额外开一面。)

证明一下该判定方法的正确性：由于式子2的$p$是贪心下最小方案，因此如果超出左边界肯定是不合法的，而右边界仔细想想就会发现其实是不会存在超出的情况的，因此判断时只要判左边界就行了

现在题目给出了$m$，问$\min\{p\}$，于是我们可以枚举$k$，分别累加计算$p$并判断它是否合法

复杂度及证明：

复杂度$O(cnt*\min\{m\})$，其中$cnt$是种类数

最劣情况显然是所有$m$都相等，此时$m=\frac{n}{cnt}$

复杂度为$O(mcnt)\Leftrightarrow O(\frac{n}{cnt}cnt)\Leftrightarrow O(n)$

因此复杂度最劣情况下是$O(n)$的

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}


const int N=2e6+5;
int cnt[N],n;
vector<int> g;

int calc(int x){
    int res=0;
    for(int i=0;i<g.size();i++){
        int now=(g[i]-1)/x+1; //套用式子2
        if((x-1)*now<=g[i]) res+=now; //判定是否满足式子1（只判了左边界）
        else return INT_MAX; //不合法
    }
    return res;
}

void doit(){
    read(n);
    for(int i=1;i<=n;i++) cnt[i]=0; //清空桶
    for(int i=1,x;i<=n;i++) cnt[read(x)]++;
    g.clear();
    int mi=n;
    for(int i=1;i<=n;i++) if(cnt[i]) g.push_back(cnt[i]),mi=min(mi,cnt[i]); //记录下桶中的最少数量
    int ans=n;
    for(int i=mi+1;i>1;i--) ans=min(ans,calc(i)); //枚举单页容量，分别计算出所需面数，取个最小值
    write(ans);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}